#include "sort.h"

void _MergeSort(vector<int>& vc, vector<int>& tmp, int begin, int end);

void MergeSort(vector<int>& vc){
  vector<int> tmp;
  tmp.resize(vc.size());

  size_t gap = 1;
  while(gap < vc.size())
  {
    for(size_t i = 0; i < vc.size(); i+=2*gap)
    {
      size_t begin1 = i;
      size_t end1 = begin1+gap;
      size_t begin2 = end1;
      size_t end2 = begin2+gap;

      int k = begin1;
      if(end1 >= vc.size())
      {
        end1 = vc.size();
        while(end1-begin1 > 0)
        {
          tmp[k++] = vc[begin1++];
        }
        continue;
      }
      else if(end2 > vc.size())
      {
        end2 = vc.size();
      }
      

      while(end1-begin1>0 && end2-begin2>0)
      {
        if(vc[begin1] <= vc[begin2])
        {
          tmp[k++] = vc[begin1++];
        }
        else
        {
          tmp[k++] = vc[begin2++];
        }
      }

      while(end1-begin1 > 0)
      {
        tmp[k++] = vc[begin1++];
      }
      while(end2-begin2 > 0)
      {
        tmp[k++] = vc[begin2++];
      }
    }

    for(size_t i = 0; i<vc.size(); ++i)
    {
      vc[i] = tmp[i];
    }
    gap*=2;
  }
}

//void MergeSort(vector<int>& vc){
//  vector<int> tmp;
//  tmp.resize(vc.size());
//  _MergeSort(vc, tmp, 0, vc.size());
//}

void _MergeSort(vector<int>& vc, vector<int>& tmp, int begin, int end){
  int midi = begin+(end-begin)/2;
  int begin1 = begin;
  int end1 = midi;
  int begin2 = midi;
  int end2 = end;

  if(end1 - begin1 > 1)
  {
    _MergeSort(vc, tmp, begin1, end1);
  }
  if(end2 - begin2 > 1)
  {
    _MergeSort(vc, tmp, begin2, end2);
  }

  int k = begin;
  while(end1-begin1>0 && end2-begin2>0)
  {
    if(vc[begin1] <= vc[begin2])
    {
      tmp[k++] = vc[begin1++];
    }
    else
    {
      tmp[k++] = vc[begin2++];
    }
  }

  while(end1-begin1 > 0)
  {
    tmp[k++] = vc[begin1++];
  }
  while(end2-begin2 > 0)
  {
    tmp[k++] = vc[begin2++];
  }

  for(int i = begin; i<end; ++i)
  {
    vc[i] = tmp[i];
  }
}
